#include <iostream>

template<typename T>int partition(T *arr, int n);

template<typename T>int quicksort(T *arr, int n);

template<typename T>int quicksort(T *arr, int n){
  if (n>0){
    int p = partition(arr,n);
    quicksort(arr,p);
    quicksort(arr+p+1,n-p-1);
  }
  return 0;
}

template<typename T>int partition(T *arr, int n){
  if (n<=0)
    return 0;
  int left =0;
  int right = n-1;
  T pivot = arr[0];
  while (left != right){
    while (arr[right] >= pivot && right > left)
      right--;
    while (arr[left] <= pivot && right > left)
      left++;
    if (right > left){
      T tmp = arr[left];
      arr[left]=arr[right];
      arr[right]=tmp;
      right--;
    }
  }
  arr[0] = arr[left];
  arr[left] = pivot;
  return left;
}
int main(int argc, char *argv[]){
  double A[5]={3.14,1.28,2.71,2.71,8.9};
  std::cout << "Before:A=[";
  for (int i=0; i<5;i++)
    std::cout << A[i] << ",";
  std::cout <<"\b]"<< std::endl;
  quicksort(A,5);
   std::cout << "After:A=[";
  for (int i=0; i<5;i++)
    std::cout << A[i] << ",";
  std::cout <<"\b]"<< std::endl;
  return 0;
}
